//
// Description: 34. 在排序数组中查找元素的第一个和最后一个位置
// Created by Loading on 2022/4/3.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> searchRange(vector<int> &nums, int target) {
    vector<int> res(2, -1);
    int n = nums.size();
    if (!n) {
        return res;
    }

    int l = 0, r = n - 1;
    // 寻找最左边第一个大于等于target的下标
    while (l < r) {
        int mid = l + (r - l >> 1);
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    res[0] = nums[l] == target ? l : res[0];
    l = 0, r = n - 1;
    // 寻找最右边最后一个小于等于target的下标
    while (l < r) {
        int mid = l + (r - l + 1 >> 1);
        if (nums[mid] <= target) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    res[1] = nums[l] == target ? l : res[1];

    return res;
}

int main() {
    vector<int> nums{5, 7, 7, 8, 8, 10};
    int target = 8;
    auto res = searchRange(nums, target);
    cout << res[0] << ' ' << res[1] << endl;

    return 0;
}